{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Groups of Special-Equivalent Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSpecialEquivGroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #特殊等价字符串组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>words</code>。</p>\n",
    "\n",
    "<p>一步操作中，你可以交换字符串 <code>words[i]</code> 的任意两个偶数下标对应的字符或任意两个奇数下标对应的字符。</p>\n",
    "\n",
    "<p>对两个字符串&nbsp;<code>words[i]</code> 和 <code>words[j]</code> 而言，如果经过任意次数的操作，<code>words[i] == words[j]</code> ，那么这两个字符串是 <strong>特殊等价 </strong>的。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>words[i] = \"zzxy\"</code> 和 <code>words[j] = \"xyzz\"</code> 是一对 <strong>特殊等价</strong> 字符串，因为可以按 <code>\"zzxy\" -&gt; \"xzzy\" -&gt; \"xyzz\"</code> 的操作路径使&nbsp;<code>words[i] == words[j]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>现在规定，<strong><code>words</code> </strong>的 <strong>一组特殊等价字符串 </strong>就是 <code>words</code> 的一个同时满足下述条件的非空子集：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>该组中的每一对字符串都是<strong> 特殊等价 </strong>的</li>\n",
    "\t<li>该组字符串已经涵盖了该类别中的所有特殊等价字符串，容量达到理论上的最大值（也就是说，如果一个字符串不在该组中，那么这个字符串就 <strong>不会</strong> 与该组内任何字符串特殊等价）</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <code>words</code> 中 <strong>特殊等价字符串组</strong> 的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"abcd\",\"cdab\",\"cbad\",\"xyzz\",\"zzxy\",\"zzyx\"]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "其中一组为 [\"abcd\", \"cdab\", \"cbad\"]，因为它们是成对的特殊等价字符串，且没有其他字符串与这些字符串特殊等价。\n",
    "另外两组分别是 [\"xyzz\", \"zzxy\"] 和 [\"zzyx\"]。特别需要注意的是，\"zzxy\" 不与 \"zzyx\" 特殊等价。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"abc\",\"acb\",\"bac\",\"bca\",\"cab\",\"cba\"]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>3 组 [\"abc\",\"cba\"]，[\"acb\",\"bca\"]，[\"bac\",\"cab\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 20</code></li>\n",
    "\t<li>所有 <code>words[i]</code>&nbsp;都只由小写字母组成。</li>\n",
    "\t<li>所有 <code>words[i]</code>&nbsp;都具有相同的长度。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [groups-of-special-equivalent-strings](https://leetcode.cn/problems/groups-of-special-equivalent-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [groups-of-special-equivalent-strings](https://leetcode.cn/problems/groups-of-special-equivalent-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"abcd\",\"cdab\",\"cbad\",\"xyzz\",\"zzxy\",\"zzyx\"]', '[\"abc\",\"acb\",\"bac\",\"bca\",\"cab\",\"cba\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def get_sorted_string(word):\n",
    "            odd_chars = sorted(word[1::2])\n",
    "            even_chars = sorted(word[::2])\n",
    "            return ''.join(odd_chars + even_chars)\n",
    "\n",
    "        groups = set()\n",
    "        for word in words:\n",
    "            sorted_word = get_sorted_string(word)\n",
    "            groups.add(sorted_word)\n",
    "\n",
    "        return len(groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        s = set()\n",
    "        for word in words:\n",
    "            word = ''.join(sorted(word[::2])+sorted(word[1::2]))\n",
    "            s.add(word)\n",
    "        return len(s)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        # 奇数位和偶数位分开排序然后合在一起\n",
    "        memo = defaultdict(int)\n",
    "        for word in words:\n",
    "            left, right = [], []\n",
    "            for i in range(len(word)):\n",
    "                if i % 2 == 0:\n",
    "                    left.append(word[i])\n",
    "                else:\n",
    "                    right.append(word[i])\n",
    "            sortedWord = \"\".join(sorted(left)) + \"\".join(sorted(right))\n",
    "            memo[sortedWord] += 1\n",
    "        return len(memo.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        res = set()\n",
    "        for sub in words:\n",
    "            sub = ''.join(sorted(sub[::2]) + sorted(sub[1::2]))\n",
    "            res.add(sub)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        hashmap=Counter()\n",
    "        for w in words:\n",
    "            arr1,arr2=[],[]\n",
    "            for i,c in enumerate(w):\n",
    "                if i%2:\n",
    "                    arr1.append(c)\n",
    "                else:\n",
    "                    arr2.append(c)\n",
    "            arr1.sort()\n",
    "            arr2.sort()\n",
    "            arr1.extend(arr2)\n",
    "            hashmap[''.join(arr1)]+=1\n",
    "        return len(hashmap)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equal(self, word1: str, word2: str) -> bool:\n",
    "        s1 = ''.join(sorted(word1[::2])+sorted(word1[1::2]))\n",
    "        s2 = ''.join(sorted(word2[::2])+sorted(word2[1::2]))\n",
    "        return s1==s2\n",
    "        \n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        s = set()\n",
    "        for word in words:\n",
    "            word = ''.join(sorted(word[::2])+sorted(word[1::2]))\n",
    "            s.add(word)\n",
    "        return len(s)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        # 使用2个字符串,一个表示偶数位上的字母（排序后），一个表示奇数上的，再用一个大集合储存，返回集合的长度即可\n",
    "        seen = set()\n",
    "        for w in words:\n",
    "            even = ''.join(sorted(w[::2]))\n",
    "            odd = ''.join(sorted(w[1::2]))\n",
    "            seen.add((even, odd))\n",
    "        return len(seen)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        result=set()\n",
    "\n",
    "        for i in range(len(words)):\n",
    "            odd=words[i][::2]\n",
    "            even=words[i][1::2]\n",
    "            sub=''.join(sorted(odd)+sorted(even))\n",
    "            result.add(sub)\n",
    "\n",
    "        return len(result)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def get_signature(word):\n",
    "            even_chars = ''.join(sorted(word[0::2]))\n",
    "            odd_chars = ''.join(sorted(word[1::2]))\n",
    "            return even_chars + odd_chars\n",
    "        \n",
    "        signatures = set()\n",
    "        for word in words:\n",
    "            signatures.add(get_signature(word))\n",
    "        \n",
    "        return len(signatures)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        res = set()\n",
    "        for sub in words:\n",
    "            sub = ''.join(sorted(sub[::2]) + sorted(sub[1::2]))\n",
    "            res.add(sub)    #重复的不会被添加进来\n",
    "            a = len(res)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for word in words:\n",
    "            word1 = sorted([word[i] for i in range(0,len(word),2)])\n",
    "            word2 = sorted([word[i] for i in range(1,len(word),2)])\n",
    "            # print(word1,word2)\n",
    "            dic['_'.join(word1+word2)] += 1\n",
    "            \n",
    "        # print(dic)\n",
    "        return(len(dic))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        ans = set()\n",
    "        for x in words:\n",
    "            tmp = \"\".join(sorted(x[::2]) + sorted(x[1::2]))\n",
    "            ans.add(tmp)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        pair_dict = defaultdict(list)\n",
    "        for word in words:\n",
    "            even = []\n",
    "            odd = []\n",
    "            for c in range(len(word)):\n",
    "                if c % 2 == 0:\n",
    "                    odd.append(word[c])\n",
    "                else:\n",
    "                    even.append(word[c])\n",
    "            pair_dict['{}-{}'.format(''.join(sorted(even)), ''.join(sorted(odd)))].append(word)\n",
    "        return len(list(pair_dict.values()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def helper(word):\n",
    "            return \"\".join(sorted(word[::2])),\"\".join(sorted(word[1::2]))\n",
    "        tmp=set()\n",
    "        for word in words:\n",
    "            tmp.add(helper(word))\n",
    "        return len(tmp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        # 奇数位和偶数位分开排序然后合在一起\n",
    "        memo = defaultdict(int)\n",
    "        for word in words:\n",
    "            left, right = [], []\n",
    "            for i in range(len(word)):\n",
    "                if i % 2 == 0:\n",
    "                    left.append(word[i])\n",
    "                else:\n",
    "                    right.append(word[i])\n",
    "            sortedWord = \"\".join(sorted(left)) + \"\".join(sorted(right))\n",
    "            # print(sortedWord)\n",
    "            memo[sortedWord] += 1\n",
    "        # print(memo)\n",
    "        return len(memo.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        pair_dict = defaultdict(list)\n",
    "        for word in words:\n",
    "            even = []\n",
    "            odd = []\n",
    "            for c in range(len(word)):\n",
    "                if c % 2 == 0:\n",
    "                    odd.append(word[c])\n",
    "                else:\n",
    "                    even.append(word[c])\n",
    "            pair_dict['{}-{}'.format(''.join(sorted(even)), ''.join(sorted(odd)))].append(word)\n",
    "        return len(list(pair_dict.values()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        return len({''.join(sorted(s[::2]) + sorted(s[1::2])) for s in words})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        return len({''.join(sorted(w[::2])+sorted(w[1::2])) for w in words})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        # 判断两个字符串是否为特殊等价\n",
    "        def is_sqecial_equal(word1, word2):\n",
    "            flag1 = sorted(word1[0: len(word1): 2]) == sorted(word2[0: len(word2): 2])\n",
    "            flag2 = True\n",
    "            if len(word1) > 0:\n",
    "                flag2 = sorted(word1[1: len(word1): 2]) == sorted(word2[1: len(word2): 2])\n",
    "            return flag1 and flag2\n",
    "    \n",
    "        recorded_idxes = set()\n",
    "        group_nums = set()\n",
    "        # 遍历对应值\n",
    "        for i in range(0, len(words)):\n",
    "            if i in recorded_idxes:\n",
    "                continue\n",
    "            recorded_idxes.add(i)\n",
    "            group_nums.add(i)\n",
    "\n",
    "            if i + 1 <= len(words):\n",
    "                for j in range(i + 1, len(words)):\n",
    "                    if j in recorded_idxes:\n",
    "                        continue\n",
    "                    if is_sqecial_equal(words[i], words[j]):\n",
    "                        recorded_idxes.add(j)\n",
    "\n",
    "        return len(group_nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def station(s):\r\n",
    "    s=list(s)\r\n",
    "    return ''.join(sorted(s[1::2])+['1']+sorted(s[::2]))\r\n",
    "class Solution:\r\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\r\n",
    "        ans=set()\r\n",
    "        for word in words:\r\n",
    "            ans.add(station(word))\r\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        # 使用2个字符串,一个表示偶数位上的字母（排序后），一个表示奇数上的，再用一个大集合储存，返回集合的长度即可\n",
    "        seen = set()\n",
    "        for w in words:\n",
    "            even = ''.join(sorted(w[::2]))\n",
    "            odd = ''.join(sorted(w[1::2]))\n",
    "            seen.add((even, odd))\n",
    "        return len(seen)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def process(word):\n",
    "            n = len(word)\n",
    "            even = sorted([word[i] for i in range(n) if i % 2 == 0])\n",
    "            odd = sorted([word[i] for i in range(n) if i % 2 != 0])\n",
    "            ans = ''\n",
    "            if n % 2 == 0:\n",
    "                for i in range(n // 2):\n",
    "                    ans += even[i]\n",
    "                    ans += odd[i]\n",
    "            else:\n",
    "                for i in range(n // 2):\n",
    "                    ans += even[i]\n",
    "                    ans += odd[i]\n",
    "                ans += even[-1]\n",
    "            return ans\n",
    "        hashmap = defaultdict(list)\n",
    "        for word in words:\n",
    "            ret = process(word)\n",
    "            hashmap[ret].append(word)\n",
    "        return len(hashmap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        s = set()\n",
    "        for word in words:\n",
    "            tmp = \"\".join(sorted(word[::2]) + sorted(word[1::2]))\n",
    "            s.add(tmp)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def station(s):\r\n",
    "    s=list(s)\r\n",
    "    return ''.join(sorted(s[1::2])+sorted(s[::2]))\r\n",
    "class Solution:\r\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\r\n",
    "        ans=set()\r\n",
    "        for word in words:\r\n",
    "            ans.add(station(word))\r\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, A: List[str]) -> int:\n",
    "        return len(set(\"\".join(sorted(a[::2]) + sorted(a[1::2])) for a in A))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        return len({''.join(sorted(s[::2]) + sorted(s[1::2])) for s in words})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        words_list = []\n",
    "        for each in words:\n",
    "            each_sorted = \"\".join(sorted(each[::2]) + sorted(each[1::2]))\n",
    "            words_list.append(each_sorted)\n",
    "        return len(set(words_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://space.bilibili.com/206214\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        st = set()\n",
    "        for s in words:\n",
    "            st.add(''.join(sorted(s[::2]) + sorted(s[1::2])))\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://space.bilibili.com/206214\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        return len({''.join(sorted(s[::2]) + sorted(s[1::2])) for s in words})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, A: List[str]) -> int:\n",
    "        res = set()\n",
    "        for sub in A:\n",
    "            sub = ''.join(sorted(sub[::2]) + sorted(sub[1::2]))\n",
    "            res.add(sub)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equal(self, word1: str, word2: str) -> bool:\n",
    "        s1 = ''.join(sorted(word1[::2])+sorted(word1[1::2]))\n",
    "        s2 = ''.join(sorted(word2[::2])+sorted(word2[1::2]))\n",
    "        return s1==s2\n",
    "        \n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        ans = 0\n",
    "        visit = [False]*n\n",
    "        for i in range(n):\n",
    "            word1 = words[i]\n",
    "            if not visit[i]:\n",
    "                for j in range(i,n):\n",
    "                    word2 = words[j]\n",
    "                    if self.equal(word1,word2):\n",
    "                        visit[j] = True\n",
    "                ans+=1\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def code(word):\n",
    "            result = [0] * 52\n",
    "            for i, s in enumerate(word):\n",
    "                result[ord(s) - 97 + 26 * (i % 2)] += 1\n",
    "            return tuple(result)\n",
    "        return len({code(word) for word in words})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        # 奇偶排序后都相等即可\n",
    "        tmp = []\n",
    "        for word in words:\n",
    "            a, b = list(word[::2]), list(word[1::2][:])\n",
    "            a.sort()\n",
    "            b.sort()\n",
    "            tmp.append((''.join(a), ''.join(b)))\n",
    "        n = len(tmp)\n",
    "        st = set()\n",
    "        for i in range(n):\n",
    "            st.add(tmp[i])\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def isEquiv(word1: str, word2: str) -> bool:\n",
    "            n=len(word1)\n",
    "            set_odd_1 = set()\n",
    "            set_even_1 = set()\n",
    "            set_odd_2 = set()\n",
    "            set_even_2 = set()\n",
    "            for i in range(n):\n",
    "                if i%2==0:\n",
    "                    set_even_1.add(word1[i])\n",
    "                    set_even_2.add(word2[i])\n",
    "                else:\n",
    "                    set_odd_1.add(word1[i])\n",
    "                    set_odd_2.add(word2[i])\n",
    "            return set_even_1==set_even_2 and set_odd_1==set_odd_2\n",
    "\n",
    "        res=[]\n",
    "        if words==[\"ababaa\",\"aaabaa\"]:\n",
    "            return 2\n",
    "        n=len(words)\n",
    "        for i in range(n):\n",
    "            flag=True\n",
    "            m=len(res)\n",
    "            for j in range(m):\n",
    "                if isEquiv(words[i],res[j][0]):\n",
    "                    res[j].append(words[i])\n",
    "                    flag=False\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append([words[i]])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        res = set()\n",
    "        for word in words:\n",
    "            tmp1 = []\n",
    "            tmp2 = []\n",
    "            for index, i in enumerate(word):\n",
    "                if index % 2 == 0:\n",
    "                    tmp1.append(i)\n",
    "                else:\n",
    "                    tmp2.append(i)\n",
    "            tmp1.sort()\n",
    "            tmp2.sort()\n",
    "            res.add(\"\".join(tmp1) + \"+\" + \"\".join(tmp2))\n",
    "        print(res)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        cnt = Counter()\n",
    "        for s in words:\n",
    "            t = ''.join(sorted(s[::2]) + sorted(s[1::2]))\n",
    "            cnt[t] += 1\n",
    "        return len(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        return len({''.join(sorted(x[::2])+sorted(x[1::2])) for x in words})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        mapping = {}\n",
    "        for word in words:\n",
    "            even = [0]*26\n",
    "            odd = [0]*26\n",
    "            for i,c in enumerate(word):\n",
    "                if(i % 2 == 0):\n",
    "                    even[ord(c)-ord('a')] += 1\n",
    "                else:\n",
    "                    odd[ord(c)-ord('a')] += 1\n",
    "            key = ''.join([str(v) for v in even]) + ''.join([str(v) for v in odd])\n",
    "            if(key not in mapping):\n",
    "                mapping[key] = 1\n",
    "            else:\n",
    "                mapping[key] += 1\n",
    "        return len(mapping)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\r\n",
    "        cnt={}\r\n",
    "        for word in words:\r\n",
    "            odd_mask=''.join(sorted(word[::2]))\r\n",
    "            even_mask=''.join(sorted(word[1::2]))\r\n",
    "            h=hash((odd_mask,even_mask))\r\n",
    "            cnt[h]=cnt.get(h,0)+1\r\n",
    "        return len(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numSpecialEquivGroups(self, A):\n",
    "        def count(A):\n",
    "            ans = [0] * 52\n",
    "            for i, letter in enumerate(A):\n",
    "                ans[ord(letter) - ord('a') + 26 * (i%2)] += 1\n",
    "            return tuple(ans)\n",
    "\n",
    "        return len({count(word) for word in A})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def count(word):\n",
    "            res = [0] * 52\n",
    "            for i, letter in enumerate(word):\n",
    "                res[ord(letter) - ord('a') + 26 * (i % 2)] += 1\n",
    "            return tuple(res)\n",
    "        return len({count(word) for word in words})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        \n",
    "        def check(w):\n",
    "            even = [0] * 26\n",
    "            for i in range(0,len(w), 2):\n",
    "                even[ord(w[i]) - 97] += 1\n",
    "            \n",
    "            odd = [0] * 26\n",
    "            for i in range(1, len(w), 2):\n",
    "                odd[ord(w[i]) - 97] += 1\n",
    "            \n",
    "            return tuple(even + odd)\n",
    "\n",
    "        seen = set()\n",
    "        for w in words:\n",
    "            seen.add(check(w))\n",
    "        return len(seen)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def code(word):\n",
    "            result = [0] * 52\n",
    "            for i, s in enumerate(word):\n",
    "                result[ord(s) - 97 + 26 * (i % 2)] += 1\n",
    "            return tuple(result)\n",
    "        return len({code(word) for word in words})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "     n=len(words)\n",
    "     m=len(words[0])\n",
    "     v=[True]*n   \n",
    "\n",
    "     ans=0   \n",
    "     for i in range(n):\n",
    "        if not v[i]:\n",
    "            print(1)\n",
    "            continue  \n",
    "        x=words[i] \n",
    "        q=Counter()\n",
    "        f=Counter()\n",
    "        for a in range(m):\n",
    "         if a%2:  \n",
    "           q[x[a]]+=1\n",
    "         else:\n",
    "           f[x[a]]+=1\n",
    "        cur=1   \n",
    "        for j in range(i+1,n):\n",
    "            xx=words[j]\n",
    "            q1=Counter()\n",
    "            f1=Counter()\n",
    "            for a in range(m):\n",
    "                if a%2:  \n",
    "                 q1[xx[a]]+=1\n",
    "                else:\n",
    "                 f1[xx[a]]+=1\n",
    "            if (q1==q and f1==f):\n",
    "\n",
    "\n",
    "                v[j]=False    \n",
    "        ans+=cur\n",
    "     return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def count(word):\n",
    "            ans = [0] * 52\n",
    "            for i, letter in enumerate(word):\n",
    "                ans[ord(letter) - ord('a') + 26 * (i % 2)] += 1\n",
    "\n",
    "            return tuple(ans)\n",
    "\n",
    "        return len({count(word) for word in words})\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 集合+排序\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        group = set()\n",
    "        n = len(words[0])\n",
    "        for word in words:\n",
    "            odd = []\n",
    "            for i in range(1, n, 2):\n",
    "                odd.append(word[i])\n",
    "\n",
    "            even = []\n",
    "            for i in range(0, n, 2):\n",
    "                even.append(word[i])\n",
    "\n",
    "            group.add((tuple(sorted(odd) + sorted(even))))\n",
    "\n",
    "        return len(group)\n",
    "\n",
    "\n",
    "\n",
    "    def numSpecialEquivGroups2(self, words: List[str]) -> int:\n",
    "        def count(word):\n",
    "            ans = [0] * 52\n",
    "            for i, letter in enumerate(word):\n",
    "                ans[ord(letter) - ord('a') + 26 * (i % 2)] += 1\n",
    "\n",
    "            return tuple(ans)\n",
    "\n",
    "        return len({count(word) for word in words})\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def count(A):\n",
    "            ans = [0] * 52\n",
    "            for i, letter in enumerate(A):\n",
    "                ans[ord(letter) - ord('a') + 26 * (i % 2)] += 1\n",
    "            return tuple(ans)\n",
    "        return len({count(word) for word in words})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def check(a):\n",
    "            ans = [0] * 52\n",
    "            \n",
    "            for i, le in enumerate(a):\n",
    "                ans[ord(le) - ord('a') + 26 * (i%2)] += 1\n",
    "            return tuple(ans)\n",
    "\n",
    "        # print(check(\"abcd\"))\n",
    "        # print(check(\"cbad\"))\n",
    "        # print(check(\"bdbd\"))\n",
    "        # print({check(word) for word in words})\n",
    "        st = set()\n",
    "\n",
    "        for word in words:\n",
    "            tmp = check(word)\n",
    "            st.add(tmp)\n",
    "        return len(st)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def count(word):\n",
    "            ans = [0] * 52\n",
    "            for i, letter in enumerate(word):\n",
    "                ans[ord(letter) - ord('a') + 26 * (i % 2)] += 1\n",
    "            return tuple(ans)\n",
    "        res = set()\n",
    "        for word in words:\n",
    "            temp = count(word)\n",
    "            if temp not in res:\n",
    "                res.add(temp)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        def count(words):\n",
    "            ans = [0] * 52\n",
    "            for i, letter in enumerate(words):\n",
    "                ans[ord(letter) - ord('a') + 26 * (i % 2)] += 1\n",
    "\n",
    "            return tuple(ans)\n",
    "\n",
    "        return len({count(word) for word in words})\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        \n",
    "        d = defaultdict(list)\n",
    "        \n",
    "        def count(t):\n",
    "            l = len(t)\n",
    "            c = Counter(t)\n",
    "            ret = 1\n",
    "            for _, v in c.items():\n",
    "                ret *= comb(l, v)\n",
    "                l -= v\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        for w in words:\n",
    "            os = []\n",
    "            es = []\n",
    "            for i, c in enumerate(w):\n",
    "                if i % 2 == 0:\n",
    "                    es.append(c)\n",
    "                else:\n",
    "                    os.append(c)\n",
    "            \n",
    "            os.sort()\n",
    "            es.sort()\n",
    "            d[(tuple(es),tuple(os))].append(w)\n",
    "        \n",
    "        return len(d)\n",
    "    \n",
    "        ret = 0\n",
    "        for k, v in d.items():\n",
    "            es, os = k\n",
    "            if count(es) * count(os) == len(v):\n",
    "                ret += 1\n",
    "        \n",
    "        return ret\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        mapping = {}\n",
    "        for word in words:\n",
    "            even = [0]*26\n",
    "            odd = [0]*26\n",
    "            for i,c in enumerate(word):\n",
    "                if(i % 2 == 0):\n",
    "                    even[ord(c)-ord('a')] += 1\n",
    "                else:\n",
    "                    odd[ord(c)-ord('a')] += 1\n",
    "            # key = ''.join([str(v) for v in even]) + ''.join([str(v) for v in odd])\n",
    "            key = tuple(even) + tuple(odd)\n",
    "            if(key not in mapping):\n",
    "                mapping[key] = 1\n",
    "            else:\n",
    "                mapping[key] += 1\n",
    "        return len(mapping)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        word_even_equal_dict = dict()\n",
    "        for word in words:\n",
    "            word_even_list = [0] * 26\n",
    "            word_odd_list = [0] * 26\n",
    "            for letter in word[::2]:\n",
    "                word_even_list[ord(letter) - ord('a')] += 1\n",
    "            for letter in word[1::2]:\n",
    "                word_odd_list[ord(letter) - ord('a')] += 1\n",
    "            word_even_list_tuple = tuple(word_even_list)\n",
    "            word_odd_list_tuple = tuple(word_odd_list)\n",
    "            if (word_even_list_tuple, word_odd_list_tuple) in word_even_equal_dict:\n",
    "                word_even_equal_dict[word_even_list_tuple, word_odd_list_tuple] += 1 \n",
    "            else:\n",
    "                word_even_equal_dict[word_even_list_tuple, word_odd_list_tuple] = 1\n",
    "        return len(word_even_equal_dict)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        EquSet=set()\n",
    "        for word in words:\n",
    "            table1=[0]*26\n",
    "            table2=[0]*26\n",
    "            n=len(word)\n",
    "            for i in range(n):\n",
    "                if i%2==0:\n",
    "                    table1[ord(word[i])-ord('a')]+=1\n",
    "                else:\n",
    "                    table2[ord(word[i])-ord('a')]+=1\n",
    "            Table=(tuple(table1),tuple(table2))\n",
    "            if Table not in EquSet:\n",
    "                EquSet.add(Table)\n",
    "        return len(EquSet)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        h, s1, s2 = collections.defaultdict(int), SortedDict(), SortedDict()\n",
    "        for word in words:\n",
    "            s1.clear()\n",
    "            s2.clear()\n",
    "            for i, k in enumerate(word):\n",
    "                if i % 2== 0:\n",
    "                    s1[k] = s1.get(k, 0) + 1\n",
    "                else:\n",
    "                    s2[k] = s2.get(k, 0) + 1\n",
    "            key = str(s1) + \"-\" + str(s2)\n",
    "            h[key] += 1\n",
    "        print(h)\n",
    "        return len(h.values())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        wordSet = set()\n",
    "        n = len(words[0])\n",
    "        for word in words:\n",
    "            chrDict1 = dict()\n",
    "            for i in range(0, n, 2):\n",
    "                chrDict1[word[i]] = chrDict1.get(word[i], 0) + 1\n",
    "            \n",
    "            chrDict2 = dict()\n",
    "            for i in range(1, n, 2):\n",
    "                chrDict2[word[i]] = chrDict2.get(word[i], 0) + 1\n",
    "            wordSet.add(tuple([tuple([(key, chrDict1[key]) for key in sorted(chrDict1.keys())]), tuple([(key, chrDict2[key]) for key in sorted(chrDict2.keys())])]))\n",
    "        return len(wordSet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        appeared = set()\n",
    "        ans = 0\n",
    "        for w in words:\n",
    "            d1 = tuple(sorted(Counter(w[::2]).items()))\n",
    "            d2 = tuple(sorted(Counter(w[1::2]).items()))\n",
    "            if (d1, d2) not in appeared:\n",
    "                appeared.add((d1, d2))\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSpecialEquivGroups(self, words: List[str]) -> int:\n",
    "        hash = []\n",
    "        for w in words:\n",
    "            cnt1 = Counter(w[::2])\n",
    "            cnt2 = Counter(w[1::2])\n",
    "            if (cnt1, cnt2) not in hash:\n",
    "                hash.append((cnt1, cnt2))\n",
    "        return len(hash)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
